# 链表
# 链表是由一系列节点组成的元素集合。每个节点包含两部分，数据域item和指向下一个节点的指针next。通过节点之间的相互连接，最终串联成一个链表。
class Node(object):
    def __init__(self, item, p=None):
        self.item = item
        # 如果不传指针就是None
        self.next = p


a = Node(1)
b = Node(2)
c = Node(3)
a.next = b
b.next = c
print(a.next.item)


# 链表操作
class Linkedlist(object):
    # 操作初始化，定义头节点 尾插法
    def __init__(self, data):
        if len(data) != 0:
            self.head = Node(data[0])
            p = self.head
            for i in data[1:]:
                node = Node(i)
                p.next = node
                p = node
        else:
            print('链表初始化为空')

    # 初始化链表 尾插法
    def init_list(self, data):
        if len(data) != 0:
            self.head = Node(data[0])
            p = self.head
            for i in data[1:]:
                node = Node(i)
                p.next = node
                p = node
        else:
            print('链表初始化为空')

    # 获取链表长度
    def get_length(self):
        p = self.head
        if p:
            sum = 1
            while p.next:
                sum = sum + 1
                p = p.next
            return sum
        else:
            return 0

    # 判断链表是否为空
    def is_empty(self):
        if self.get_length() == 0:
            return True
        else:
            return False

    # 获取节点数据的值
    def get_item(self, index):
        if self.is_empty():
            print('链表为空')
            return
        p = self.head
        i = 0
        while p.next:
            if i == index:
                return p.item
            p = p.next
            i = i + 1
        else:
            if i == index:
                return p.item

    # 单链表的添加操作,尾部添加
    def append(self, item):
        # 待添加节点
        q = Node(item)
        if self.head == 0:
            self.head = q
        else:
            p = self.head
            while p.next:
                p = p.next
            p.next = q

    # 链表数据插入
    def insert(self, index, item):
        if self.is_empty():
            print('链表为空')
            return
        # 如果插入的位置是第一个位置将该节点指针指向原来的第一个节点
        if index <= 0:
            q = Node(item, self.head)
            self.head = q
        # 如果插入的位置大于链表的长度，添加到链表的尾部
        elif index >= self.get_length():
            self.append(item)
        else:
            q = Node(item)
            p = self.head
            i = 0
            while p.next:
                if i == index - 1:
                    t = p.next
                    p.next = q
                    q.next = t
                    break
                p = p.next
                i = i + 1

    # 链表数据的删除根据索引
    def delete_index(self, index):
        if self.is_empty():
            print('链表为空')
            return
        elif index <= 0:
            self.head = self.head.next
        else:
            if index >= self.get_length():
                index = self.get_length() - 1
            p = self.head
            i = 0
            while p.next:
                if i == index - 1:
                    # 指针跳过删除的对象，指向到被删除的节点的下个节点
                    p.next = p.next.next
                    break
                p = p.next
                i = i + 1

    # 根据链表的值来删除数据
    def delete_item(self, item):
        p = self.head
        if p.item == item:
            self.head = p.next
            return
        i = 0
        while p.next:
            if p.next.item == item:
                p.next = p.next.next
                break
            p = p.next
            i = i + 1

    # 链表数据遍历
    def show(self):
        p = self.head
        while p.next:
            print('item = ', p.item)
            p = p.next
        print('item = ', p.item)


lk = Linkedlist([10, 20, 30, 40, 50, 60, 70, 80, 91])
print('链表长度是：', lk.get_length())
# print('链表的遍历：', lk.show())
lk.insert(7, 100)
# lk.append(100)
# lk.show()
# lk.delete_index(6)
# lk.show()
# print(lk.get_item(6))
# lk.delete_item(10)
lk.show()

# # 创建链表
# # 头插法，由于是倒序所以只需要head
# def create_head_linkedlist(li):
#     head = Node(li[0])
#     for element in li[1:]:
#         node = Node(element)
#         node.next = head
#         head = node
#     return head
#
#
# # 尾插法,由于链表只有next所以需要head和next来维护
# def create_tail_linkedlist(li):
#     head = Node(li[0])
#     tail = head
#     for element in li[1:]:
#         node = Node(element)
#         tail.next = node
#         tail = node
#     return head
#
#
# # 链表的遍历
# def print_linkedlist(lk):
#     while lk is not None:
#         print(lk.item, end=',')
#         lk = lk.next
#
#
# lk = create_head_linkedlist([1, 2, 3])
# lk1 = create_tail_linkedlist([1, 2, 3, 4, 5, 6, 77, 77, 21])
# print_linkedlist(lk)
# print_linkedlist(lk1)
